// @algorithm @lc id=42 lang=cpp 
// @title trapping-rain-water


// #define print(...)
// @test([0,1,0,2,1,0,1,3,2,1,2,1])=6
// @test([4,2,0,3,2,5])=9
class Solution {
public:
    int trap(vector<int>& height) {
        list<int> stk;
        int capacity = 0;
        for(int right=0; right<height.size(); right++){
            while(stk.size() && height[stk.back()] < height[right]){
                int bottom = stk.back(); stk.pop_back(); if(stk.empty()) break;
                int left   = stk.back();
                capacity  += (right - left - 1) * (min(height[left], height[right]) - height[bottom]);
            }
            stk.push_back(right);
        }
        return capacity;
    }
};